//题目:
// 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
// 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
// 如果 x == y，那么两块石头都会被完全粉碎；
// 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
// 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int lastStoneWeightII(vector<int>& stones) 
    {
        //题意转换：只需找到最接近sum/2的目标值即可
        int sum=0,n=stones.size();
        for(int i=0;i<n;i++)
            sum+=stones[i];
        int target=sum%2==1?sum/2+1:sum/2;
        // //1.创建dp表————dp[i][j]表示：选到第i个元素，和为j的情况是否存在
        // vector<vector<bool>> dp(n+1,vector<bool>(target+1));
        // //2.初始化
        // for(int i=0;i<=n;i++) dp[i][0]=true;
        // //3.填表 
        // for(int i=1;i<=n;i++)
        // {
        //     for(int j=1;j<=target;j++)
        //         if(dp[i-1][j]==true || (j-stones[i-1]>=0 && dp[i-1][j-stones[i-1]]==true))
        //             dp[i][j]=true;
        // }
        // //4.确定返回值
        // for(int i=target;i>=0;i--)
        //     if(dp[n][i]==true)
        //         return abs(sum-2*i);
        // return 0;

        //优化
        //1.创建dp表————dp[i][j]表示：选到第i个元素，和为j的情况是否存在
        vector<bool> dp(target+1);
        //2.初始化
        dp[0]=true;
        //3.填表 
        for(int i=1;i<=n;i++)
            for(int j=target;j>=stones[i-1];j--)
                if(dp[j-stones[i-1]]==true)
                    dp[j]=true;

        //4.确定返回值
        for(int i=target;i>=0;i--)
            if(dp[i]==true)
                return abs(sum-2*i);
        return 0;
    }
};